//给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。 
//
// 计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。 
//
// 你可以认为每种硬币的数量是无限的。 
//
// 
//
// 示例 1： 
//
// 
//输入：coins = [1, 2, 5], amount = 11
//输出：3 
//解释：11 = 5 + 5 + 1 
//
// 示例 2： 
//
// 
//输入：coins = [2], amount = 3
//输出：-1 
//
// 示例 3： 
//
// 
//输入：coins = [1], amount = 0
//输出：0
// 
//
// 
//
// 提示： 
//
// 
// 1 <= coins.length <= 12 
// 1 <= coins[i] <= 2³¹ - 1 
// 0 <= amount <= 10⁴ 
// 
//
// Related Topics 广度优先搜索 数组 动态规划 👍 2680 👎 0


package com.tyrone.leetcode.editor.cn;

import java.util.*;

public class CoinChange{
    public static void main(String[] args) {
       Solution solution = new CoinChange().new Solution();
        System.out.println(solution.coinChange(new int[]{1,2,5}, 11));
    }
    //leetcode submit region begin(Prohibit modification and deletion)
class Solution {
        /**
         * 广度优先 每一层都是    假设coins是   1,2,3
         *                       0
         *           1           2            3
         *       1  2  3     1  2  3       1  2  3
         *    123 123 123  123 123 123  123 123 123
         *
         *  所以直接使用广度优先，如果能组合出来，就直接返回，由于是一层一层下去的，所以肯定是最小的
         *  上一次提交超时，由于没有使用顺序所以 1-2-3 和 2-1-3和 3-2-1 都是一样
         *  对于求解 amount 7 来说这三个路径（和）重合了,和都是一样的所以只用求一个就可以了
         *  用一个list来存储访问的过路径
         *  还是超时了tmd 那就换种方法
         *
         *  用了动态规划，但是一开始填充用的是MaxInt，但是过程中因为arr[i-coins[j]]+1 里面的+1 导致溢出了 然后导致出问题
         * @param coins
         * @param amount
         * @return
         */
        public int coinChange(int[] coins, int amount){
            int INF = 0x3f3f3f3f;
            int[] dp = new int[amount+1];
            for (int i = 1; i <= amount; i++) dp[i] = INF;
            for (int i =0; i < coins.length; i++) {
                int curr = coins[i];
                for (int j = curr; j < amount + 1; j++) {
                    //不选择
                    int n = dp[j];
                    //这里其实没有必要去判断j - coins[i] >= 0 因为这个条件一定是True的
                    int y = j - coins[i] >= 0? dp[j - coins[i]] + 1 : 0;
                    dp[j] = Math.min(n, y);
                }
            }
            return dp[amount] ==INF?-1:dp[amount];
        }
//        public int coinChange(int[] coins, int amount){
//            int n = coins.length;
//            int[][] dp = new int[n][amount+1]; // dp[i][j]  表示 在0～i商品内，选择的价值等于j的最小数量
//            for (int i = 0; i < amount + 1; i++) {
//                dp[0][i] = i == 0 ? 0:i%coins[0]==0?i/coins[0]:Integer.MAX_VALUE;
//            }
//            for (int i = 1; i < n; i++) {
//                int curr = coins[i];
//                for (int j = 0; j < amount + 1; j++) {
//                    //不选择当前硬币
//                    dp[i][j] = dp[i-1][j];
//                    for (int k=1;k*curr<=j;k++){
//                        if (dp[i-1][j-k*curr]!=Integer.MAX_VALUE)
//                            dp[i][j]=Math.min(dp[i][j],dp[i-1][j-k*curr]+k);  //这里之前我一直用的是+ k*curr 这样算的就是价值，但这里要算的是硬币数应该是+k
//                    }
//                }
//            }
//            return dp[n-1][amount] == Integer.MAX_VALUE?-1:dp[n-1][amount];
//        }

//        public int coinChange(int[] coins, int amount) {
//            if (amount==0) return 0;
//            if (coins.length==1 && amount%coins[0]!=0) return -1;
//            int[] arr = new int[amount+1];
//
//            Arrays.fill(arr,amount+1);
//            arr[0] = 0;
//            for (int i = 1; i <= amount; i++) {
//                for (int j = 0; j < coins.length; j++) {
//                    //看了别人题解，这里是可以优化，有可能i-coins[j]都是不可到达的，就没有必要判断了 提交了之后发现更慢了 就算了
//                    if (i>=coins[j] ){
//                        arr[i] = Math.min(arr[i],arr[i-coins[j]]+1);
//                    }
//                }
//            }
//            return arr[amount] ==amount+1? -1: arr[amount];
//        }
//    public int coinChange(int[] coins, int amount) {
//        if (amount==0) return 0;
//        Queue<Integer> queue = new LinkedList<>();
//        queue.offer(0);
//        List<Integer> list = new ArrayList<>();
//        list.add(0);
//        int nums = 0;
//        while (!queue.isEmpty()){
//            int size = queue.size();
//            nums++;
//            for (int i = 0; i < size; i++) {
//                Integer curr = queue.poll();
//                for (int coin : coins) {
//                    int now = curr + coin;
//                    if (now == amount){
//                        return nums;
//                    }else if (now<amount && !list.contains(now)){
//                        queue.offer(now);
//                        list.add(now);
//                    }
//                }
//            }
//        }
//        return -1;
//    }
}
//leetcode submit region end(Prohibit modification and deletion)

}